/*
* leetcode 918. 环形子数组的最大和
*
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
/*
* */
import java.util.*;
class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n=nums.length,sum=0,max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;
        int[] f=new int[n+1],g=new int[n+1];
        for(int i=1;i<=n;i++){
            int x=nums[i-1];
            //更新数组中的连续最大和
            f[i]=Math.max(f[i-1]+x,x);
            max=Math.max(f[i],max);
            //更新数组中的连续最小和
            g[i]=Math.min(g[i-1]+x,x);
            min=Math.min(g[i],min);
            sum+=x;
        }
        //如果取首尾相连的话，中间就会被一个连续子数组切割开
        //此时最大值就为数组元素和减去中间最小连续子数组和即可
        return sum==min?max:Math.max(max,sum-min);
    }
}